//题目:
// 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
// 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
// 例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
#include<iostream>
#include<vector>

using namespace std;
//代码:
class Solution 
{
    int ret=0;
    int arr[20001]={0};//备忘录
public:
    //计算以pos位置为起始的最长递增子序列
    int dfs(vector<int>& nums,int pos,int prev)
    {
        if(arr[pos]!=0)return arr[pos];

        int ret=1;
        for(int i=pos+1;i<nums.size();i++)
        {
            if(nums[i]>prev)
            {
                ret=max(ret,1+dfs(nums,i,nums[i]));
            }
        }

        arr[pos]=ret;
        return ret;
    }
    int lengthOfLIS(vector<int>& nums) 
    {
        int ret=0;
        for(int i=0;i<nums.size();i++)
            ret=max(ret,dfs(nums,i,nums[i]));
        return ret;
    }
};